// 给定一个二叉树，我们在树的节点上安装摄像头。

// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

// 计算监控树的所有节点所需的最小摄像头数量。

//  

// 示例 1：



// 输入：[0,0,null,0,0]
// 输出：1
// 解释：如图所示，一台摄像头足以监控所有节点。
// 示例 2：



// 输入：[0,0,null,0,null,0,null,null,0]
// 输出：2
// 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

// 提示：

// 给定树的节点数的范围是 [1, 1000]。
// 每个节点的值都是 0。

#include "stdc++.h"

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/*
状态 a：root 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
状态 b：覆盖整棵树需要的摄像头数目，无论 root 是否放置摄像头。
状态 c：覆盖两棵子树需要的摄像头数目，无论节点 root 本身是否被监控到。
*/
struct Status {
    int a{0};
    int b{0};
    int c{0};
};

class Solution {
public:
    int minCameraCover(TreeNode* root) {
        Status s = dfs(root);
        return s.b;
    }
    Status dfs(TreeNode* root) {
        if (root == nullptr) {
            return {INT_MAX / 2, 0, 0};
        }
        auto ls = dfs(root->left);
        auto rs = dfs(root->right);
        int a = ls.c + rs.c + 1;
        int b = min(a, min(ls.a + rs.b, ls.b + rs.a));
        int c = min(a, ls.b + rs.b);
        return {a, b, c};
    }
};